
\chapter{Trees}

\label{chapter:trees}


This chapter describes procedures available for manipulating trees.  The
term \iix{tree} is used in a technical sense to refer to non-circular
list structure considered as tree data-structures, as contrasted with
{\it lists\/}, which use chained pairs to represent a one-dimensional
sequence of objects.  Thus one might say either that {\mbox {\tt (A (B C) D)}} is
a list of three elements, or that it is a tree with four (non-null)
leaves.

Trees are used to represent programs.  The tree-manipulation
procedures and special forms are designed with this in mind.

\section{Comparison}

\index{equality predicates}

\index{EQUIV?@{\tt EQUIV?}}
{\mbox {\tt (EQUIV? {\it object1 object2\/}) $\longrightarrow$\  {\it boolean\/}}}
\hfill  

\begin{inset}{}
{\tt EQUIV?} is an equality predicate, not for comparing trees but for
comparing leaves.

\begin{itemize}
\item[{}]If {\tt (EQ? {\it object1\/} {\it object2\/})}, then
{\tt (EQUIV? {\it object1\/} {\it object2\/})}.

\item[{}]If {\it object1\/} and {\it object2\/} are both numbers of the same type,
then they are {\tt EQUIV?} iff they have the same numeric value
(see {\tt =}, page \pageref{EQUAL?}).

\item[{}]If {\it object1\/} and {\it object2\/} are both strings,
then they are {\tt EQUIV?} if they are {\tt STRING-EQUAL?}
(page \pageref{STRING-EQUAL?}).
\end{itemize}
See also the descriptions of {\tt EQ?} (page \pageref{EQ?}) and {\tt =}
(page \pageref{EQUAL?}).

    \begin{inset}{Bug:}
    In {\bf T} 3.1, {\tt EQUIV?} (and {\tt ALIKEV?}) may return false
    for two numbers which are {\tt =}.  It will do the right thing,
    however, for FIXNUMs.
    \end{inset}
\end{inset} 


\index{ALIKE?@{\tt ALIKE?}}
{\mbox {\tt (ALIKE? {\it predicate tree1 tree2\/}) $\longrightarrow$\  {\it boolean\/}}}
\hfill  

\begin{inset}{}
Returns true if {\it tree1\/} and {\it tree2\/} have the same shape
and their corresponding leaves are equal according to
{\it predicate\/}, which must be an equality predicate.
\begin{codexenv}
(ALIKE? = '(1 (2 . 8) 3) '(1 (2 . 8) 3))  $\Longrightarrow$\   {\it true}
\end{codexenv}
\end{inset} 

\index{ALIKEQ?@{\tt ALIKEQ?}}
{\mbox {\tt (ALIKEQ? {\it tree1 tree2\/}) $\longrightarrow$\  {\it boolean\/}}}
\hfill  

\begin{inset}{}
\begin{codexenv}
(ALIKEQ? {\it tree1 tree2\/})  $\equiv$  (ALIKE? EQ? {\it tree1 tree2\/})
\end{codexenv}
\end{inset} 

  
\index{ALIKEV?@{\tt ALIKEV?}}
{\mbox {\tt (ALIKEV? {\it tree1 tree2\/}) $\longrightarrow$\  {\it boolean\/}}}
\hfill  

\begin{inset}{}
\begin{codexenv}
(ALIKEV? {\it tree1\/} {\it tree2\/})  $\equiv$  (ALIKE? EQUIV? {\it tree1\/} {\it tree2\/})
\end{codexenv}
Roughly speaking, two trees are {\tt ALIKEV?} if they print the
same way.
\end{inset} 

\section{Tree utilities}


\index{SUBST@{\tt SUBST}}
{\mbox {\tt (SUBST {\it predicate new old tree\/}) $\longrightarrow$\  {\it tree\/}}}
\hfill  

\begin{inset}{}
Returns a result tree which is the same as the argument {\it tree\/},
except that leaves in the argument tree which, according to
{\it predicate\/}, are equal to {\it old\/}, have been changed to be
{\it new\/}.  {\it Predicate\/} must be an equality predicate.
\begin{codexenv}
(SUBST EQUIV? 17 13 '(10 (20 13) 30))  $\Longrightarrow$\   (10 (20 17) 30)
\end{codexenv}
The result returned by {\tt SUBST} may or may not share structure with its
tree argument.
\end{inset} 

\index{SUBSTQ@{\tt SUBSTQ}}
{\mbox {\tt (SUBSTQ {\it new old tree\/}) $\longrightarrow$\  {\it tree\/}}}
\hfill  

\begin{inset}{}
\begin{codexenv}
(SUBSTQ {\it new old tree\/})  $\equiv$  (SUBST EQ? {\it new old tree\/})
\end{codexenv}
\end{inset} 

\index{SUBSTV@{\tt SUBSTV}}
{\mbox {\tt (SUBSTV {\it new old tree\/}) $\longrightarrow$\  {\it tree\/}}}
\hfill  

\begin{inset}{}
\begin{codexenv}
(SUBSTV {\it new old tree\/})  $\equiv$  (SUBST EQUIV? {\it new old tree\/})
\end{codexenv}
\end{inset} 

\index{COPY-TREE@{\tt COPY-TREE}}
{\mbox {\tt (COPY-TREE {\it tree\/}) $\longrightarrow$\  {\it tree\/}}}
\hfill  

\begin{inset}{}
Recursively make a copy of the {\it tree\/}.
\begin{codexenv}
(COPY-TREE {\it tree\/})  $\equiv$  (SUBSTQ NIL NIL {\it tree\/})
\end{codexenv}
\end{inset} 

\index{TREE-HASH@{\tt TREE-HASH}}
{\mbox {\tt (TREE-HASH {\it tree\/}) $\longrightarrow$\  {\it integer\/}}}
\hfill  

\begin{inset}{}
Compute a \ix{hash code} for {\it tree\/}.
The hash computed is a non-negative fixnum with the property
that if {\it tree1\/} and {\it tree2\/} are {\tt ALIKEV?},
then their hashes are the same.
\end{inset} 

\section{Destructuring}


\index{DESTRUCTURE@{\tt DESTRUCTURE}}
{\mbox {\tt (DESTRUCTURE {\it specs . body\/}) $\longrightarrow$\  {\it value-of-body\/}}}
\hfill Special form

\label{DESTRUCTURE}
\begin{inset}{}
{\it Specs\/} has the form {\mbox {\tt (({\it pattern value\/}) ({\it pattern value\/}) \ldots\ )}}
where each {\it pattern\/} is either an identifier (e.g., {\tt X})
or a {\it tree\/} (see page \pageref{chapter:trees}),
all of whose non-null leaves are identifiers
(e.g., {\mbox {\tt ((X Y . Z) P Q)}}).

{\tt DESTRUCTURE} is similar to {\tt LET}, and in the case that all the
{\it patterns\/} are symbols, {\tt DESTRUCTURE} and {\tt LET} are
equivalent. But {\tt DESTRUCTURE} is especially useful when one wants
to bind variables to the various nodes in a single tree structure.  For
example, suppose {\tt Z} has the value {\mbox {\tt (1 (2 3) ((4 5 . 6) 7))}},
and we want to bind {\tt A} to 1, {\tt B} to 2, {\tt C} to 3,
{\tt D} to 6, and {\tt E} to 7. We could write
{\tt \begin{tabbing}
(LET \= (\= (A (CAR Z)) \+ \+ \\
      (B (CAADR Z)) \\
      (C (CDADR Z)) \\
      (D (CDDAR (CADDR Z))) \\
      (E (CADADR (CDR Z)))) \- \\
  \ldots\ )
\end{tabbing}}
However, we could also write
\begin{codexenv}
(DESTRUCTURE (((A (B . C) ((() () . D) E)) Z)) \\
  \ldots\ )
\end{codexenv}
The {\tt ()}'s notate ignored positions.
\end{inset} 

\index{DESTRUCTURE*@{\tt DESTRUCTURE*}}
{\mbox {\tt (DESTRUCTURE* {\it specs . body\/}) $\longrightarrow$\  {\it value-of-body\/}}}
\hfill Special form

\begin{inset}{}
{\tt DESTRUCTURE*} is the ``serial'' form of {\tt DESTRUCTURE}, just
as {\tt LET*} is the ``serial'' form of {\tt LET}.
{\tt \begin{tabbing}
(DESTRUCTURE* \= (\= ({\it pattern$_{\hbox{1}}$ value$_{\hbox{1}}$\/}) \+ \+ \\
               ({\it pattern$_{\hbox{2}}$ value$_{\hbox{2}}$\/}) \\
               \ldots\  \\
               ({\it pattern$_{\hbox{n}}$ value$_{\hbox{n}}$\/})) \- \\
  {\it code\/}) \\
  $\equiv$ \- \\
(\= DESTRUCTURE (({\it pattern$_{\hbox{1}}$ value$_{\hbox{1}}$\/})) \+ \\
  (\= DESTRUCTURE (({\it pattern$_{\hbox{1}}$ value$_{\hbox{1}}$\/})) \+ \\
   \ldots\  \= \+ \\
     (DESTRUCTURE \= (({\it pattern$_{\hbox{n}}$ value$_{\hbox{n}}$\/})) \+ \\
       {\it code\/} )\ldots\ ))
\end{tabbing}}
\end{inset} 

\section{Quasiquote}

\label{section:quasiquote}
\index{quasiquote}\index{backquote}

{\bf T}'s {\it quasiquote\/} facility, inherited from the Maclisp family
of Lisps, is useful for building programs whose form
is determined, but where some of the structure is constant
and some is to be filled in.
This is especially convenient in the definitions of macro
expanders.
It is so useful that a special external syntax is provided
for notating such templates.
It takes its name from the name
of the character (quasiquote, ` ) which introduces this special syntax.

The character ("` ") is called {\it quasiquote\/}
because it behaves like {\tt QUOTE} except that one can specify that
subforms of the quasiquote'd form should be evaluated.  Inside a form
that is preceded by a quasiquote, two additional pieces of
external syntax are active: comma ({\tt ,}), and comma at-sign ({\tt ,@});
these are the ways to indicate that some subform should
be evaluated (i.e., unquoted).  A subform preceded by a comma
is evaluated and replaced by the result of the evaluation.
A subform preceded by a comma at-sign is evaluated and replaced
by {\it splicing in\/} the result of the evaluation.

Here are some simple examples.  Note that the first example shows code
equivalence, not evaluation.
\begin{codexenv}
    \begin{tabular}{lll}
` (A B ,X Y)  &$\equiv$&  (LIST 'A 'B X 'Y) \\

(DEFINE X '(3)) \\
(CDR ` (A B ,X C))    &$\Longrightarrow$\ &  (B (3) C) \\
(CDR ` (A B ,@X C))  &$\Longrightarrow$\ &  (B 3 C)
\end{tabular}
    \end{codexenv}

{\tt \begin{tabbing}
(DEFINE-SYNTAX \= (REPEAT N . CODE)     ;Execute CODE N times \+ \\
  ` (LET \= ((COUNT ,N) (THUNK (LAMBDA () ,@CODE))) \+ \\
     (DO \= ((COUNT COUNT (-1+ COUNT))) \+ \\
         (($<$=0? COUNT) '()) \\
       (THUNK))))
\end{tabbing}}

It is possible to nest quasiquoted forms.  This is useful when writing complex
source-to-source transformations.
{\tt \begin{tabbing}
(DEFINE-SYNTAX \= (FOO X Y) \+ \\
  ` (LET \= ((STUFF ,X)) \+ \\
     ` ((STUFF-IS ,STUFF) \\
       (Y-IS ,',Y)))) \- \- \\

(FOO (+ 3 5) BAZ)  $\Longrightarrow$\   ((STUFF-IS 8) (Y-IS BAZ))
\end{tabbing}}

{\mbox {\tt quasiquote}} now works on vectors.  Thus,
\begin{codexenv}
` \#(1 2 ,(+ 1 2)) $\Longrightarrow$\  \#(1 2 3)
\end{codexenv}
